package com.fc.primary.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: fc-java->MyTree
 * @description:
 * @author: G_Y
 * @create: 2019-09-01 18:00
 * 手写二叉树
 **/
public class MyTree<T> {

    /**
     * 根节点
     */
    TreeNode<T> rootNode;

    public MyTree() {
        rootNode = new TreeNode<>();
    }

    public boolean add(T item) {
        TreeNode<T> node = new TreeNode<>();
        node.setItem(item);
        // ...
        return true;
    }

    public static class TreeNode<T> {
        T item;
        TreeNode<T> leftNode;
        TreeNode<T> rightNode;
        TreeNode<T> parentNode;

        public TreeNode() {
        }

        public TreeNode(T item, TreeNode<T> leftNode, TreeNode<T> rightNode, TreeNode<T> parentNode) {
            this.item = item;
            this.leftNode = leftNode;
            this.rightNode = rightNode;
            this.parentNode = parentNode;
        }

        public T getItem() {
            return item;
        }

        public void setItem(T item) {
            this.item = item;
        }

        public TreeNode<T> getLeftNode() {
            return leftNode;
        }

        public void setLeftNode(TreeNode<T> leftNode) {
            this.leftNode = leftNode;
        }

        public TreeNode<T> getRightNode() {
            return rightNode;
        }

        public void setRightNode(TreeNode<T> rightNode) {
            this.rightNode = rightNode;
        }

        public TreeNode<T> getParentNode() {
            return parentNode;
        }

        public void setParentNode(TreeNode<T> parentNode) {
            this.parentNode = parentNode;
        }
    }

    private List<TreeNode> result = new ArrayList<TreeNode>();

    // 前序遍历方法 【根左右】
    public void preOrder(TreeNode node) {
        result.add(node);
        if (node.getLeftNode() != null) {
            preOrder(node.getLeftNode());
        }
        if (node.getRightNode() != null) {
            preOrder(node.getRightNode());
        }
    }

    // 中序遍历法【左根右】
    public void inOrder(TreeNode node) {
        if (node.getLeftNode() != null) {
            inOrder(node.getLeftNode());
        }
        result.add(node);
        if (node.getRightNode() != null) {
            inOrder(node.getRightNode());
        }
    }

    // 后序遍历法【左右根】
    public void postOrder(TreeNode node) {
        if (node.getLeftNode() != null) {
            postOrder(node.getLeftNode());
        }
        if (node.getRightNode() != null) {
            postOrder(node.getRightNode());
        }
        result.add(node);
    }
}
